/* 
 * File:   sort.h
 * Author: Yinhaochuan
 *
 * Created on 2013年9月27日, 下午11:18
 */

#ifndef SORT_H
#define	SORT_H
#include<iostream>
using namespace std;

void swap(int &a,int &b)
{
    if(a!=b)
    {
    a = a^b;
    b = a^b;
    a = a^b;
    }
}

void print(int arr[],int length)
{
    for(int i=0;i<length;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

void bubbleSort(int arr[],int length)
{
    for(int i=0;i<length;i++)
    {
        for(int j=i+1;j<length;j++)
        {
            if(arr[j]<arr[i])
                swap(arr[j],arr[i]);
        }
    }    
}

void selectSort(int arr[],int length)
{
    for(int i=0;i<length;i++)
    {
        int nMin = i;
        for(int j=i+1;j<length;j++)
        {
            if(arr[j]<arr[nMin])
                nMin = j;
        }
        swap(arr[i] , arr[nMin]);
    }
}

void insertSort(int arr[],int length)
{
       int j =0 ;
    for(int i=1;i<length;i++)
    {
        if(arr[i]<arr[i-1])
        {        
            int temp = arr[i];
            for(j=i-1;j>=0&&arr[j]>temp;j--)
            {
                swap(arr[j+1],arr[j]);
            }
            arr[j+1] =temp;
        }
      
    }
}

void shellSort(int arr[],int length)
{
    for(int gap=length/2;gap>0;gap/=2)
    {
        for(int i=0;i<gap;i++)
        {
            for(int j=i+gap;j<length;j+=gap)
            {
                if(arr[j]<arr[j-gap])
                {
                    int temp = arr[j];
                    int k = j-gap;
                    while(k>=0&&arr[k]>temp)
                    {
                        arr[k+gap] = arr[k];
                        k-=gap;
                    }
                    arr[k+gap] = temp;
                }
            }
        }
    }
}

void quickSort(int arr[],int left,int right)
{
    cout<<"here"<<endl;
    if(left<right)
    {
        int i=left;
        int j=right;
        int X = arr[left];
        while(i<j)
        { 
            while(i<j&&arr[j]>=X)
            {
                j--;
            }
            if(i<j)
            {
                arr[i++] = arr[j];
            }
            while(i<j&&arr[i]<X)
            {
                i++;
            }
            if(i<j)
            {
                arr[j++] = arr[i];
            }
        }
        arr[i]=X;        
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
}

void mergeOrderlyArr(int arr[],int left,int mid,int right,int temp[])
{
    int i= left;
    int m = mid;
    int j = mid+1;
    int n = right;
    int k=0;
    while(i<=m&&j<=n)
    {
        if(arr[i]<=arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while(i<=m)
    {  
        temp[k++] = arr[i++];
    }
    while(j<=n)
    {
        temp[k++] = arr[j++];
    }    
    for(i=0;i<k;i++)
    {
        arr[left+i] = temp[i];
    }
}

void mergeSort(int arr[],int left,int right,int temp[])
{
    if(left<right)
    {
        int mid = (left+right)/2;
        mergeSort(arr,left,mid,temp);
        mergeSort(arr,mid+1,right,temp);
        mergeOrderlyArr(arr,left,mid,right,temp);
    }        
}
void mergeSORT(int arr[],int length)
{
    int *p = new int[19];
    if(!p)
        return;
    mergeSort(arr,0,length-1,p);
    delete[] p;
}
#endif	/* SORT_H */

